Logical objects (such as files and directories) comprise a collection of logical data blocks which correspond to physical data blocks in the computer storage. Logical data blocks in a logical object are commonly organized using block maps for mapping offsets within an object to respective block addresses within a related logical volume. Such a block map may be included in a metadata structure (e.g. index node, or Mode) that describes the logical object or can be referred by the Mode. The block map can be a hierarchical mapping data structure, e.g. a B-Tree. For example in a B-tree data structure, the Mode serves as the root of the tree, and each leaf in the tree points to either a data block or extent of blocks. The information of this block map is stored in metadata blocks.
Updating logical objects in a file system usually requires several separate operations, which expose the update process to possible system interruption resulting for example from a power failure or a system crash (referred herein in general as “system interruption”). A system interruption that occurs between writes of a deletion process may result in data structures, used for storing data blocks of respective objects, which are left in an invalid intermediate state.
For example a file deletion operation in a Unix file system typically involves the steps of: (i) removing the file's directory entry; (ii) marking the blocks associated with the file (including actual data blocks and metadata blocks) as free in a free space map; and (iii) marking the Mode entry of the file as free. Deletion of the blocks associated with an object involves scanning a mapping data-structure (e.g. a B-Tree block map) that holds all the data and metadata blocks of the object in order to delete each block included in that data-structure. A storage leak may occur, for example, if the Mode was marked as free but not all the blocks were marked as free, and a system interruption occurs during the deletion process of an object before all blocks have been deleted.
Some file systems are programmed to run consistency checks in order to obtain consistency of the file system after a system interruption. Typically, after the system restarts and before the file system is mounted for read and write access the file system executes a complete walk through the file system's data structures. For example, Linux and UNIX systems use fsck (file system consistency check) command to check file system consistency and repair it while Microsoft Windows equivalent commands are CHKDSK_and SCANDISK. This process is time and resource consuming.
Some file systems use Journaling, where changes that are going to be made in each transaction are recorded in a journal file before committing the changes to the main file system. For example all changes that are going to be made as part of a file deletion (all data blocks and metadata blocks to be deleted, the Mode entry to be freed, etc.) are written as one entry in the journal file. When the system is restarted after a system interruption, the transactions in the journal may be replayed or rolled back. Journaling file systems accelerate the time taken to repair the system, but have the disadvantage of increasing file-system operation latency and performing additional I/O operations for writing the journal.
Thus, there is a need in the art for additional solutions enabling to perform object deletion while maintaining data consistency and avoid memory leaks in case of a system interruption.